package cn.genmer.test.security.algorithm.sort;

import java.util.Arrays;

/**
 * @program: java8stream
 * @description:
 * @author: Genmer
 * @create: 2021-07-13 22:54
 **/
public class InsertSort {
    public static void main(String[] args) {
        int[] a = { 9,1,5,6,2,3 };
        int[] sorted = insertSort(a);
        System.out.println(Arrays.toString(sorted));
    }

    /**
     * 插入排序 2022.11.18
     * @param arr
     */
    public static void sort(int[] arr){
        int size = arr.length;
        for (int i=1; i<size; i++){
            for (int j=i; j>0 && arr[j] < arr[j-1]; j--){
//                if (arr[j] < arr[j-1]) {
                    swap(arr, j,j-1);
//                }
            }
        }
    }

    /**
     * 插入排序 优化1 去除swap方法
     * @param arr
     */
    public static void sort1(int[] arr){
        int size = arr.length;
        for (int i=0; i<size; i++){
            int temp = arr[i];
            int j = i - 1;
            for (; j>= 0 && temp < arr[j]; j--){
                arr[j+1] = arr[j];
            }
            arr[j+1] = temp;
        }
    }
    /**
     * 插入排序 优化1 去除swap方法 直接copy https://blog.csdn.net/hcz666/article/details/126488359
     * @param arr
     */
    public static void sort2(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            int insertValue = arr[i];
            int j = i - 1;
            //从右向左比较元素的同时，进行元素复制
            for(; j >=0 && insertValue < arr[j]; j--){
                arr[j+1] = arr[j];
            }
            //insertValue的值插入适当位置
            arr[j+1] = insertValue;
        }
    }

    /**
     * 老早写的版本
     * @param a
     * @return
     */
    public static int[] insertSort(int[] a){

        int[] arr = Arrays.copyOf(a, a.length);

        int length = arr.length;
        if (length <= 1){
            return arr;
        }
        for (int i=1; i<length;i++){ //{ 9,1,5,6,2,3 }  => { 1 5 6 9 9 3 }
            int index = i;
            int tmp = arr[i];

            if (arr[i] < arr[i-1]){
                while (index > 0 && tmp < arr[index - 1]){
                    arr[index] = arr[index - 1];
                    index --;
                }
                if (i != index){
                    arr[index] = tmp;
                }
            }
        }
        return arr;
    }

    /**
     * 测试记忆版本
     * 【2022.11.20】【初始】通过
     *               【优化1】不通过， （temp < arr[j]）条件这里没整清楚，用j和j+1在比较 && >=0 老是忘=
     *  2022.11.24 [初始]不通过, j初始错误 j=i, 挤成j=i-1
     *              [优化1] j>=0 老是忘=
     *  2022.11.24 [初始]   通过
     *              [优化1] 通过 TIPS 有一次j+1写成 j++
     *  2022.11.30 [优化1] 通过 TIPS 有一次j+1写成 j++, 还有内层循环j--老是写成j++
     * @param arr
     */
    public static void sortTEST(int[] arr){
        int size = arr.length;
        for (int i = 1; i < size; i++) {
            int temp = arr[i];
            int j = i-1;
            for (; j >=0 && temp < arr[j]; j--) {
                arr[j+1] = arr[j];
            }
            arr[j+1] = temp;
        }
    }


    private static void swap(int[] arr, int pos1, int pos2){
        int temp = arr[pos1];
        arr[pos1] = arr[pos2];
        arr[pos2] = temp;
    }
}
